package com.nowcoder.topic.tree.middle;

import java.util.ArrayList;

/**
 * NC415 不同的二叉搜索树(二)
 * @author d3y1
 */
public class NC415 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return TreeNode类ArrayList
     */
    public ArrayList<TreeNode> BSTgenerate (int n) {
        return dp(1, n);
    }

    /**
     * 动态规划 + 递归
     *
     * dp(m,n)表示区间[m,n]节点构成互不相同二叉搜索树的种类
     *
     * dp(m,n) = dp(m,m-1)*dp(m+1,n) + dp(m,m)*dp(m+2,n) + ... + dp(m,n-1)*dp(n+1,n)
     *
     * @param m
     * @param n
     * @return
     */
    private ArrayList<TreeNode> dp(int m, int n){
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();

        if(m > n){
            // 必须
            list.add(null);
            return list;
        }

        for(int i=m; i<=n; i++){
            ArrayList<TreeNode> leftRoots = dp(m, i-1);
            ArrayList<TreeNode> rightRoots = dp(i+1, n);

            for(TreeNode lRoot: leftRoots){
                for(TreeNode rRoot: rightRoots){
                    TreeNode root = new TreeNode(i);
                    root.left = lRoot;
                    root.right = rRoot;

                    list.add(root);
                }
            }
        }

        return list;
    }

    private class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}
